The present invention relates generally to content addressable memories (CAMs) and more particularly to CAMs having indicators for showing when an entry is occupied or unoccupied.
Due to the increasing importance of data networks, including the Internet, the prevalence of content addressable memories (CAMs) has continued to proliferate. CAMs, also referred to as xe2x80x9cassociative memories,xe2x80x9d can provide rapid matching functions that are often needed in certain packet processing hardware devices, such as routers and network switches, to name just two. In a typical packet processing operation, a device can receive a packet. The packet can include a xe2x80x9cheaderxe2x80x9d that includes various data fields that indicate how the packet should be processed. The device can use a matching function, provided by a CAM, to compare one or more header fields to xe2x80x9clook-upxe2x80x9d tables stored in the CAMs.
As just one example, a router can use a matching function to match the destination of an incoming packet with a xe2x80x9cforwardingxe2x80x9d table. The forwarding table can provide xe2x80x9cnexthopxe2x80x9d information that can allow the incoming packet to be transmitted to its final destination, or to another node on the way to its final destination.
The look-up tables in packet processing devices (which are typically stored in a CAM) are rarely static. That is, the entries with such a table may be constantly updated with different information. This may be particularly true in routers, which can update forwarding tables thousands of times a second.
A typical CAM can store the data values of a look-up table in one or more CAM cell arrays. The CAM cell arrays can be configured into a number of entries, each of which can provide a match indication. In a compare (i.e., match) operation, the data values stored within the entries can be compared to a comparand value (also referred to as a xe2x80x9csearch keyxe2x80x9d). In a typical packet processing device, the comparand value can include a field extracted from a data packet header. If a data value matches an applied comparand value, the corresponding entry can generate an active match indication. If a data value does not match an applied comparand value, the corresponding entry can generate an inactive match indication (signifying a xe2x80x9cmismatchxe2x80x9d) condition.
Because the data values within a CAM may be continuously updated, some conventional CAMs can include a xe2x80x9cstatusxe2x80x9d bit (sometimes referred to as a xe2x80x9cvalid/invalidxe2x80x9d or xe2x80x9coccupied/unoccupiedxe2x80x9d bit). A status bit can be stored in one or more CAM cells in an entry. A status bit can have a xe2x80x9cvalidxe2x80x9d logic state that can indicate an entry that stores usable data. A status bit can also have an xe2x80x9cinvalidxe2x80x9d logic state that can indicate that the data stored within contains data that should no longer be used in a compare operation.
The use of a valid/invalid bit may be best understood by an example. Referring now to FIG. 8, an example of a CAM having entries with status bits is set forth in a table form. The CAM is designated by the general reference character 800, and is shown to include eight entries, labeled 0 to 7. Each entry can include 68 bits, labeled xe2x80x9cCxe2x80x9d to 67. Bit 0 (the xe2x80x9cCxe2x80x9d bit) can be a status bit. Also shown in FIG. 8 is a 68-bit comparand value. Each entry can generate a match indication in response to the application of a comparand value.
For many CAM applications it can be desirable to have entries arranged with a predetermined priority. In the event two or more match indications are activated in response to an applied comparand value, one of the match indications can be selected according to the location of its corresponding entry. As just one example, in the particular arrangement of FIG. 8, lower numbered entries can have priority over higher numbered entries. Thus, if the application of a comparand value resulted in entries 1 and 4 both activating a match indication, the match indication of entry 1 would have priority over that of entry 4.
In the particular example of FIG. 8, bit 0 is a status bit. When the status bit is xe2x80x9c1xe2x80x9d, the entry is xe2x80x9cvalidxe2x80x9d (or occupied), and thus stores data that can be compared with a comparand value. When the status bit is xe2x80x9c0xe2x80x9d, the entry is xe2x80x9cinvalidxe2x80x9d (or unoccupied), and thus stores data that should not be compared with a comparand value. To prevent an invalid entry from generating a possibly erroneous active match indication, the bit 0 of all applied comparands is set to xe2x80x9c1.xe2x80x9d In this way, all invalid entries can be forced to generate a mismatch indication in response to a comparand value.
Thus, in the particular arrangement of FIG. 8, entries 2, 3 and 6 will generate a mismatch indication regardless of what other data values are stored within the entries.
In a table update operation, various operations can occur within a CAM. Existing xe2x80x9cvalidxe2x80x9d data values may be placed into an invalid state by writing into at least the status bit and changing it from a valid to an invalid state. In addition, new data values may be written into available entries. Available entries can be those entries with xe2x80x9cinvalidxe2x80x9d status bits.
In many applications, it can be desirable to write new data values into the xe2x80x9cnext freexe2x80x9d entry. A next free entry can be the lowest number entry that is invalid. In the particular arrangement of FIG. 8, entry 2 can be considered the next free entry.
One way to write data into a xe2x80x9cnext freexe2x80x9d entry is to employ duplicate storage registers to maintain a record of which entries are valid (such as a xe2x80x9cshadow registerxe2x80x9d). A lowest entry number can then be determined from these values. The next free location can then be used as a write address for a subsequent data value write.
Approaches that utilize duplicate storage registers can have a number of drawbacks. Testing may become more complicated as data stored in the entry and the data in duplicate registers must both be tested to ensure that they both store the same data.
Approaches with xe2x80x9cshadow registersxe2x80x9d can also result in defective operation if either the entries or the duplicate registers contain a defect. Still further, such approaches can consume additional area on an integrated circuit, in addition to the area consumed by the registers themselves. Still further, additional circuitry can be included to write data into and read data out of the duplicate registers as well as ancillary support circuitry. Still further, other circuitry may be included to select the next free location from the shadow register information.
It would be desirable to arrive at some way of identifying a next free location in a CAM that is less complicated and/or consumes less circuit area than other conventional approaches.
According to disclosed embodiments, a content addressable memory (CAM) includes a number of entries that can store data values. In response to an applied comparand value, each entry can generate a match indication. The match indications can be received by a priority encoder that can select and output the address of one active match indication from multiple active match indications. Each entry can also include associated status data. Status data can indicate whether the data stored within an entry is valid or not. The priority encoder can further receive status data, and select a next free address location from the status data.
According to one aspect of the embodiments, a CAM can include a number of entries that each provide a match indication and include a CAM cell that stores status data. Match indications and status data from the CAM cells can be applied to the same priority encoder.
According to another aspect of the embodiments, a CAM can include a switch circuit that couples either match indications or status data to a priority encoder. In response to match indication, the priority encoder can generate a highest priority match indication which is output as an address. In response to status data, the priority encoder can generate a next free address. According to another aspect, a switch circuit can include multiplexer circuits.
According to another aspect of the embodiments, a CAM can automatically provide a next free address following a data write to an entry.
An advantage of the disclosed embodiments is that a CAM can provide a next free address without having to include duplicate storage registers.
An advantage of the disclosed embodiments is that a CAM that provides a next free address can be more compact than conventional approaches.